package fun.ticsmyc.question;

/**
 * @author Ticsmyc
 * @date 2021-03-25 10:45
 */
public class 约瑟夫环问题 {
    /**
     * 模拟链表来做
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        Node dum = new Node(-1);
        Node cur=dum;
        for(int i=1;i<=n;++i){
            Node c = new Node(i);
            cur.next =c;
            cur=cur.next;
        }
        cur.next = dum.next;
        Node pre = cur;
        cur=cur.next;

        while(cur.next != cur){
            for(int i=1;i<m;++i){
                cur=cur.next;
                pre=pre.next;
            }
            pre.next =cur.next;
            cur =pre.next;
        }
        return cur.val;

    }


    /** 数学方法
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int ysf2 (int n, int m) {
        // write code here
        int res = 0;
        for(int i = 2; i <= n; i++)
            res = (res + m) % i;
        return res + 1;
    }

}

class Node{
    int val;
    Node next;
    public Node(int v){
        this.val =v;
    }
}
